/*
https://leetcode.cn/problems/similar-string-groups/solutions/584001/c-ping-ping-wu-qi-bing-cha-ji-by-eddiezh-3ym0/
*/


class Solution {
public:
    vector<int> parent;  // 并查集中的父节点数组
    int count;  // 记录当前连通分量的数量

    // 合并操作
    void Union(vector<int> &parent, int a, int b) {
        int roota = Find(parent, a);  // 找到 a 的根节点
        int rootb = Find(parent, b);  // 找到 b 的根节点
        if (roota == rootb) return;  // 如果 a 和 b 已经在同一个集合中，直接返回
        parent[rootb] = roota;  // 将 b 的根节点指向 a 的根节点
        count--;  // 连通分量数量减 1
    }

    // 查找操作，带路径压缩
    int Find(vector<int> &parent, int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];  // 路径压缩
            x = parent[x];
        }
        return x;
    }

    // 判断两个字符串是否相似
    bool isSimilar(string a, string b) {
        int len = a.size();
        int diff = 0;
        for (int i = 0; i < len; i++) {
            if (a[i] != b[i]) {
                diff++;
            } 
            if (diff > 2) {
                return false;  // 如果不同的字符超过 2 个，说明不相似
            } 
        }
        return true;  // 不同的字符不超过 2 个，说明相似
    }

    // 主函数，计算相似字符串组的数量
    int numSimilarGroups(vector<string>& strs) {
        count = strs.size();  // 初始时每个字符串都是一个独立的集合
        for (int i = 0; i < strs.size(); i++) {
            parent.push_back(i);  // 初始化并查集，每个节点的父节点是自己
        }

        // 遍历所有字符串对，检查是否相似
        for (int i = 0; i < (strs.size() - 1); i++) {
            for (int j = i + 1; j < strs.size(); j++) {
                if (isSimilar(strs[i], strs[j])) {
                    if (parent[i] != parent[j]) {  // 如果不在同一个集合中
                        Union(parent, i, j);  // 合并这两个集合
                    }
                }
            }
        }

        return count;  // 返回最终的连通分量数量
    }
};